/**
 * 给定字符串S，问能否划分为K个互不重叠的特殊子串，满足
 * 1. 每个子串的任何字母都不在字符串的其他位置出现
 * 2. 子串不能是整个字符串
 * 显然主要是第1个条件，首先对每个字母记录出现的位置数组，记作Pos
 * Pos[0]到Pos[25]
 * 其次，对每个Pos[i]：
 *   如果Pos[i]中出现了其他字母，记作j，则需要用Pos[j]的首尾去更新Pos[i]
 *   这个步骤类似于BellmanFord算法，最差是O(26^2 * logN)
 * 因此这一步最差是O(26^3 * logN)
 * 
 * 然后得到的就是互不相干的若干个区间，排序去重，最多26个元素，然后做一个深搜即可。
 * 深搜过程中用Range进行管理，每一步最多O(log26)。
 * 再加上一个简单的剪枝，19ms。
 * 
 * 另外注意特判0和第2个条件。
 * 注意区间在预处理阶段和搜索阶段的处理。
 * 
 * 有更快的解法
 * 预处理以后可以对区间按右端点排序，然后从左向右贪心的合并，只需O(26log26)。
 * 
 * 还可以DP，令Di表示到Si为止互不重叠子串的数量
 * Di = D[i - 1], 不存在以i结尾的特殊子串
 * Di = max(D[i - 1], D[j - 1] + 1)，从j到i是一个特殊子串
 * O(26^2)即可
 * 实际上j无需遍历，只需要找到一个离i最近的j即可，可以边更新边记录，O(26)即可。
 */

namespace OY {
    template <typename Tp>
    struct RangeManager {
        struct Ignore {
            template <typename... Args>
            void operator()(Args...) const {}
        };
        using table_type = RangeManager<Tp>;
        using iterator = typename std::map<Tp, Tp>::iterator;
        using const_iterator = typename std::map<Tp, Tp>::const_iterator;
        Tp m_length = 0;
        std::map<Tp, Tp> m_segs;
        static Tp length_of(const std::pair<Tp, Tp> &range) { return range.second - range.first + 1; }
        template <typename AddCallback = Ignore, typename RemoveCallback = Ignore>
        void add_range(std::pair<Tp, Tp> range, AddCallback &&add_call = AddCallback(), RemoveCallback &&remove_call = RemoveCallback()) {
            auto it = upper_bound(range.first);
            if (it != begin()) {
                if ((--it)->second + 1 >= range.first) {
                    if (it->second >= range.second) return;
                    remove_call(range.first = it->first, it->second), m_length -= length_of(*it);
                    it = m_segs.erase(it);
                } else
                    ++it;
            }
            for (; it != end() && it->first <= range.second + 1; it = m_segs.erase(it)) {
                if (it->second > range.second) range.second = it->second;
                remove_call(it->first, it->second), m_length -= length_of(*it);
            }
            add_call(range.first, range.second), m_length += length_of(*m_segs.emplace(range.first, range.second).first);
        }
        template <typename AddCallback = Ignore, typename RemoveCallback = Ignore>
        void remove_range(std::pair<Tp, Tp> range, AddCallback &&add_call = AddCallback(), RemoveCallback &&remove_call = RemoveCallback()) {
            std::vector<std::pair<Tp, Tp>> deleted, inserted;
            iterator it = m_segs.upper_bound(range.first);
            if (it != begin()) {
                if ((--it)->second >= range.first) {
                    remove_call(it->first, it->second), m_length -= it->second - it->first + 1;
                    if (it->second >= range.second && it->second > range.second) {
                        add_call(range.second + 1, it->second), m_length += it->second - range.second;
                        m_segs.emplace(range.second + 1, it->second);
                        if (it->first < range.first) {
                            it->second = range.first - 1;
                            add_call(it->first, it->second), m_length += it->second - it->first + 1;
                            ++it;
                        } else
                            m_segs.erase(it);
                        return;
                    }
                    if (it->first < range.first) {
                        it->second = range.first - 1;
                        add_call(it->first, it->second), m_length += it->second - it->first + 1;
                        ++it;
                    } else
                        it = m_segs.erase(it);
                } else
                    ++it;
            }
            for (; it != end() && it->first <= range.second; it = m_segs.erase(it)) {
                remove_call(it->first, it->second), m_length -= it->second - it->first + 1;
                if (it->second > range.second) m_segs.emplace(range.second + 1, it->second), add_call(range.second + 1, it->second), m_length += it->second - range.second;
            }
        }
        const_iterator any_of(const std::pair<Tp, Tp> &range) const {
            const_iterator it = upper_bound(range.second);
            if (it == begin()) return end();
            if ((--it)->second < range.first) return end();
            return it;
        }
        const_iterator all_of(const std::pair<Tp, Tp> &range) const {
            const_iterator it = upper_bound(range.second);
            if (it == begin()) return end();
            if ((--it)->first > range.first || it->second < range.second) return end();
            return it;
        }
        Tp length() const { return m_length; }
        void clear() { m_segs.clear(), m_length = 0; }
        auto size() const -> decltype(m_segs.size()) { return m_segs.size(); }
        auto begin() const -> decltype(m_segs.begin()) { return m_segs.begin(); }
        auto end() const -> decltype(m_segs.end()) { return m_segs.end(); }
        auto lower_bound(const Tp &key) const -> decltype(m_segs.lower_bound(key)) { return m_segs.lower_bound(key); }
        auto upper_bound(const Tp &key) const -> decltype(m_segs.upper_bound(key)) { return m_segs.upper_bound(key); }
        table_type &operator&=(const RangeManager<Tp> &rhs) {
            if (m_segs.empty() || rhs.m_segs.empty())
                clear();
            else {
                if (m_segs.begin()->first < rhs.m_segs.begin()->first) remove_range({m_segs.begin()->first, rhs.m_segs.begin()->first - 1});
                auto it = rhs.m_segs.begin(), end = rhs.m_segs.end();
                while (!m_segs.empty()) {
                    auto it2 = std::next(it);
                    if (it2 == end) {
                        auto max = std::prev(m_segs.end())->second;
                        if (max > it->second) remove_range({it->second + 1, max});
                        break;
                    }
                    remove_range({it->second + 1, it2->first - 1});
                    it = it2;
                }
            }
            return *this;
        }
        table_type &operator|=(const RangeManager<Tp> &rhs) {
            for (auto &&it : rhs) add_range(it);
            return *this;
        }
    };
    template <typename Ostream, typename Tp>
    Ostream &operator<<(Ostream &out, const RangeManager<Tp> &x) {
        out << '[';
        for (auto it = x.begin(); it != x.end(); ++it) {
            if (it != x.begin()) out << ", ";
            out << "[" << it->first << ", " << it->second << "]";
        }
        return out << ']';
    }
}

using pii = pair<int, int>;
using vpii = vector<pii>;

class Solution {

int N;
vector<vector<int>> Pos;
vpii Vec;
OY::RangeManager<int> R;

public:
    bool maxSubstringLength(string s, int k) {
        if(0 == k) return true;

        N = s.length();
        Pos.assign(26, {});
        for(int i=0;i<N;++i){
            Pos[s[i] - 'a'].emplace_back(i);
        }

        /// 对每个字母生成选中其的所需区间
        for(int i=0;i<26;++i){
            if(Pos[i].empty()){
                
            }else{
                int left = Pos[i].front();
                int right = Pos[i].back();
                while(1){
                    bool changed = false;
                    for(const auto & v : Pos){
                        if(v.empty()) continue;
                        auto at = lower_bound(v.begin(), v.end(), left);
                        auto bt = upper_bound(v.begin(), v.end(), right);
                        if(at != bt){ // 说明v中有东西在区间内，要全选
                            if(left > v.front()){
                                left = v.front();
                                changed = true;
                            }
                            if(right < v.back()){
                                right = v.back();
                                changed = true;
                            }
                        }
                    } 
                    if(not changed) break;
                }
                Vec.emplace_back(left, right);
            }
        }

        if(1 == k){
            /// 检查是否每个区间都是全体
            bool flag = false;
            for(const auto & p : Vec){
                if(p.first != 0 or p.second != N - 1){
                    flag = true; break;
                }
            }
            return flag;
        }
        if(Vec.size() < k) return false;

        sort(Vec.begin(), Vec.end(), [](const pii & a, const pii & b)->bool{
            auto an = a.second - a.first;
            auto bn = b.second - b.first;
            if(an != bn) return an < bn;
            return a.first < b.first;
        });
        Vec.erase(unique(Vec.begin(), Vec.end()), Vec.end());
        /// 在这些区间中，任选K个不想交的
        bool b = dfs(0, k);
        return b;
    }

    bool dfs(int depth, int need){
        if(0 == need) return true;
        if(Vec.size() - depth < need) return false;

        for(int i=depth;i<Vec.size();++i){
            if(R.any_of(Vec[i]) != R.end()) continue;

            R.add_range(Vec[i]);
            bool b = dfs(i + 1, need - 1);
            if(b) return true;
            R.remove_range(Vec[i]);
        }

        return false;
    }


};